首先,我們需要引入必要的庫,並定義一些輔助函數:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

// 輔助函數: 快速模冪運算
long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

// 輔助函數: 生成一個範圍內的隨機數
long long random(long long min, long long max) {
    return min + rand() % (max - min + 1);
}

接下來,我們實現ElGamal加密系統的主要部分:

class ElGamal {
private:
    long long p; // 大質數
    long long g; // 生成元
    long long x; // 私鑰
    long long y; // 公鑰

public:
    ElGamal(long long p, long long g) : p(p), g(g) {
        srand(time(NULL));
        x = random(2, p-2);  // 隨機選擇私鑰
        y = power_mod(g, x, p);  // 計算公鑰
    }

    // 加密函數
    pair<long long, long long> encrypt(long long message) {
        long long k = random(2, p-2);  // 隨機數k
        long long c1 = power_mod(g, k, p);
        long long c2 = (message * power_mod(y, k, p)) % p;
        return make_pair(c1, c2);
    }

    // 解密函數
    long long decrypt(pair<long long, long long> ciphertext) {
        long long c1 = ciphertext.first;
        long long c2 = ciphertext.second;
        long long s = power_mod(c1, x, p);
        long long s_inv = power_mod(s, p-2, p);  // 使用費馬小定理計算模逆
        return (c2 * s_inv) % p;
    }

    // 獲取公鑰
    long long get_public_key() {
        return y;
    }
};

最後,我們可以寫一個簡單的主函數來測試我們的ElGamal實現:

int main() {
    // 選擇一個大質數p和生成元g
    long long p = 23;  // 在實際應用中,這應該是一個更大的質數
    long long g = 5;

    ElGamal elgamal(p, g);

    long long message = 20;  // 要加密的消息
    cout << "原始消息: " << message << endl;

    // 加密
    pair<long long, long long> ciphertext = elgamal.encrypt(message);
    cout << "加密後: (" << ciphertext.first << ", " << ciphertext.second << ")" << endl;

    // 解密
    long long decrypted = elgamal.decrypt(ciphertext);
    cout << "解密後: " << decrypted << endl;

    return 0;
}

ElGamal加密系統的基本元素:密鑰生成、加密和解密。但請注意,這只是一個簡化的版本,。在實際應用中,你需要考慮以下幾點:

使用更大的質數p(通常至少2048位)。
實現更安全的隨機數生成器。
添加錯誤處理和輸入驗證。
考慮使用更高效的大數運算庫,如GMP(GNU Multiple Precision Arithmetic Library)。
實現填充方案以增強安全性。